/*
8.31指定起点的dfs、bfs，二部图判断。
date:20201230 am 11:10
key:
1.先弄一个连通集的，在遍历顶点。
2.
*/
#include<iostream>
#include<string>
#include<queue>
const int MAX = 1E9;
using namespace std;
void DFS(bool** mat, bool* flag, int start,int N)
{
	flag[start] = true;
	cout << start << endl;
	//start领点有没访问过的吗
	for (int i = 0; i < N; i++)
	{
		if (mat[start][i] == true)//有通路
		{
			if (flag[i] == false)//未被访问
			{
				DFS(mat, flag, i, N);;
			}
		}

		
	}
}
void BFS(bool** mat, bool* flag,  int N,queue<int>q1,int*erbutu_arr)
{
	if (!q1.empty())
	{
		int start = q1.front();
		q1.pop();
		cout << start << endl;
		//start领点有没访问过的吗
		for (int i = 0; i < N; i++)
		{
			if (mat[start][i] == true)//有通路
			{
				if (flag[i] == false)//未被访问
				{
					//push进去了就一定会被输出，所以被push了就算被访问了
					flag[i] = true;				
					q1.push(i);

				}
				if (erbutu_arr[i] == -1)//节点未填色，依据start填色
				{
					erbutu_arr[i] = (erbutu_arr[start] + 1) % 2;
				}
				else
				{
					if (erbutu_arr[i] == erbutu_arr[start])//领节点色同
					{
						cout<<"非二部图";
					}
				}
			}
		}

		//因为上面那轮都访问过的话是没有新节点push进去的
		BFS(mat, flag, N, q1,erbutu_arr);
	}

}
int main()

{

	int N, M, i, j, k, l;
	cout << "输入顶点数和边数" << endl;
	cin >> N >> M;
	//N*N领阶矩阵创建,用N+1等于不要第0列和行
	bool** mat = new bool* [N];
	for (i = 0; i < N; i++)
	{
		mat[i] = new bool[N];
	}
	//数值初始化
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			mat[i][j] = false;
		}
	}
	//输入每条路的花费
	cout << "输入顶点和输入每条路的花费" << endl;
	for (i = 0; i < M; i++)
	{
		cin >> j >> k ;
		mat[j ][k ] = true;
		//忘了这个反转术式了
		mat[k ][j ] = true;
	}
	//以0节点为起点
	int start = 0;

	//以0节点为起点的最短路径数组
	int* road = new int[N];
	for (i = 0; i < N; i++)//
	{
		road[i] = -1;
	}

	//标记数组
	bool* flag = new bool[N];
	for (i = 0; i < N; i++)//i只代表循环次数
	{
		flag[i] = false;
	}
	//图各节点是否联通的标记
	bool imposs = false;
	//从0节点开始的最短路径,只需要找n-1次
	queue<int>q1;
	int* erbutu_arr = new int[N];
	for (j = 0; j < N; j++)
	{
		if (flag[j] == false)
		{
			start=j;
			q1.push(start);
			flag[start] = true;		
			//初始化一个二部图填色数组，未染色为-1；
			for (i = 0; i < N; i++)
			{
				erbutu_arr[i] = -1;
			}
			//起点染色
			erbutu_arr[start] = 0;
			BFS(mat, flag, N, q1, erbutu_arr);
		}
		//每一次结束q1要清空
		while (!q1.empty())
		{
			q1.pop();
		}
	}

	//距离累计值,是否构不成联通图，检查标记数组。

	for (i = 0; i < N; i++)
	{

		if (flag[i] == false)
		{
			imposs = true;
			break;
		};
	}
	if (imposs)
	{
		cout << "非连通图";
	}
	else
	{
		cout << "连通图";
	}


}8.31